package com.mlh.array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
// 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。
// 请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
// 0 <= a, b, c, d < n
// a、b、c 和 d 互不相同
// nums[a] + nums[b] + nums[c] + nums[d] == target
// 你可以按任意顺序返回答案 。
//
// 输入：nums = [1,0,-1,0,-2,2], target = 0
// 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

public class FourSum {
    //写完三数之和后 独立写出
    //思路大致相同 排序+枚举+双指针  要注意和溢出
    public List<List<Integer>> method1(int[] nums, int target) {
        int n=nums.length-1;
        List<List<Integer>>res=new ArrayList<>();
        Arrays.sort(nums);
        //防止溢出
        if(nums[0]>0&&target<=0||nums[n]<0&&target>=0){
            return res;
        }
        for(int i=0;i<n-2;i++){
            if(target>0&&nums[i]>=target){
                return res;
            }
            for(int j=i+1;j<n-1;j++){
                if(target>0&&nums[i]+nums[j]>target/2){
                    break;
                }
                int left=j+1;
                int right=n;
                while (left<right){
                    if(nums[i]+nums[j]+nums[left]+nums[right]>target){
                        right--;
                    }else if(nums[i]+nums[j]+nums[left]+nums[right]<target){
                        left++;
                    }else{
                        List<Integer> temp = new ArrayList<>();
                        temp.add(nums[i]);
                        temp.add(nums[j]);
                        temp.add(nums[left]);
                        temp.add(nums[right]);
                        res.add(temp);
                        //跳过重复的数  防止答案重复
                        while (left<n&&nums[left]==nums[left+1]){
                            left++;
                        }
                        //跳过重复的数  防止答案重复
                        while (right>0&&nums[right]==nums[right-1]){
                            right--;
                        }
                        left++;
                        right--;
                    }
                }
                //跳过重复的数  防止答案重复
                while(j<n-1&&nums[j]==nums[j+1]){
                    j++;
                }
            }
            //跳过重复的数  防止答案重复
            while(i<n-2&&nums[i]==nums[i+1]){
                i++;
            }
        }
        return res;
    }
}
